#include <iostream>

using namespace std;

/*
Given a tree node structure as follows. Each Random points to any validate node in the tree.
class TreeNode
{
	int Data;
	class TreeNode *lChild;
	class TreeNode *rChild;
	class TreeNode *random;
};
Deep copy the binary tree and make the Random pointer point to the new tree node in the same 
position as the random pointer in old tree.

Algorithm:
In the solution, PrintRandomTree, CreateBT, DeleteBT are auxilury routines, 
DupOrgTree, TraverseTreeAndRestore and DuplicateTree are core routines.

1) recusive duplicate tree,  make 
   dup->random=org->random;
   org->random=dup;
2) traverse the duplicated tree, and find its own random pointer by
   dup->random=dup->random->random;
   and then restore org->random.

The question can also be applied to double linkedlist.
*/

class TreeNode
{
public:
	int Data;
	class TreeNode *lChild;
	class TreeNode *rChild;
	class TreeNode *random;
};

// this is to use the pre-order traverse to check whether the duplicate succeeds
void PrintRandomTree( TreeNode *root )
{
	if(!root) 
		return;
	PrintRandomTree( root->lChild );
	cout<<root->Data<<","<<root->random->Data<<" ";
	PrintRandomTree( root->rChild );
}

TreeNode *CreateBT( int *Array, int start, int end )
{
	//
	// Assume the Array is ordered so the new
	// created BT should be BST
	//
	if( start > end )
		return NULL;

	int middle  = start + (end-start)/2; //avoid integer overflow
	TreeNode * node = new TreeNode();
	
	node->Data = Array[middle];
    node->lChild = CreateBT( Array, start, middle-1 );
    node->rChild = CreateBT( Array, middle+1, end );
	node->random = node;   // make the random node to point itself so it is easy for test to verify

	return node;
}

void DeleteBT( TreeNode* root )
{
	if( !root )
		return;
	DeleteBT( root->lChild );
	DeleteBT( root->rChild );

	delete root;
}

void DupOrgTree( TreeNode *org, TreeNode *&dup )
{
	if(!org)
	{
		dup = NULL;
		return;
	}
	
	dup = new TreeNode();
	dup->Data = org->Data;
	DupOrgTree( org->lChild, dup->lChild);
	DupOrgTree( org->rChild, dup->rChild);
	dup->random = org->random;
	org->random = dup;
}

void TraverseTreeAndRestore( TreeNode *org, TreeNode *&dup )
{
	if( !org )
		return;

	TraverseTreeAndRestore( org->lChild, dup->lChild);
	TraverseTreeAndRestore( org->rChild, dup->rChild);
	
	TreeNode *orgRandom = dup->random;
	dup->random = dup->random->random;
	org->random = orgRandom;
}

TreeNode *DuplicateTree( TreeNode* root )
{
	TreeNode * dup = NULL;
	DupOrgTree( root, dup );
	TraverseTreeAndRestore(root, dup);
	return dup;
}

int main()
{
	int Array[10] = {1,2,3,4,5,6,7,8,9,10};
	TreeNode *root = CreateBT(Array, 0, 9);
	cout<<"Create a new random tree"<<endl;
	PrintRandomTree( root );

	TreeNode *dup = DuplicateTree(root);
	cout<<"\n\nAfter duplication, the original random tree"<<endl;
	PrintRandomTree( root );
	DeleteBT(root);

	cout<<"\n\nAfter duplication, the duplicated random tree"<<endl;
	PrintRandomTree( dup );

	cout<<"\n\nPress any key to terminate..."<<endl;
	return getchar();
}